package 竞赛.NO_406;

import java.util.Arrays;

/**
 * 创建时间：2024/7/14 上午11:23
 */
public class 切蛋糕的最小总开销I_100361 {
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        long ans = 0;
        int cm = --m - 1;
        int cn = --n - 1;
        while(cm >= 0 && cn >= 0) {
            if (horizontalCut[cm] > verticalCut[cn]) {
                ans += horizontalCut[cm--] * (n - cn);
            } else if(horizontalCut[cm] < verticalCut[cn]) {
                ans += verticalCut[cn--] * (m - cm);
            } else {
                if (horizontalCut[cm] * (n - cn) > verticalCut[cn] * (m - cm)) {
                    ans += horizontalCut[cm--] * (n - cn);
                } else {
                    ans += verticalCut[cn--] * (m - cm);
                }
            }
        }
        while(cm >= 0) {
            ans += horizontalCut[cm--] * (n - cn);
        }
        while(cn >= 0) {
            ans += verticalCut[cn--] * (m - cm);
        }
        return ans;
    }

    public static void main(String[] args) {
        切蛋糕的最小总开销I_100361 r = new 切蛋糕的最小总开销I_100361();
        System.out.println(r.minimumCost(6, 3, new int[]{2, 3, 2, 3, 1}, new int[]{1, 2}));
    }
}
